package leetcode.tree;

import java.util.HashMap;
import java.util.Locale;

public class Lc437_2 {

    HashMap<Long, Integer> preSum = new HashMap<>();
    int ans = 0;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        preSum.put(0L, 1);
        getPathSum(root, 0L, targetSum);
        return ans;
    }

    private void getPathSum(TreeNode node, long sum, int targetSum) {
        sum += node.val;
        int cnt = preSum.getOrDefault(sum - targetSum, 0);
        ans += cnt;
        preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        if (node.left != null) getPathSum(node.left, sum, targetSum);
        if (node.right != null) getPathSum(node.right, sum, targetSum);
        preSum.put(sum, preSum.get(sum) - 1);
        sum -= node.val;
    }

}
